package com.jack.leetcode.eachproblem_2020;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by zhang_j on 2020/11/11
 */
public class 自由之路 {

    public static void main(String[] args) {
        System.out.println(findRotateSteps("godding", "gd"));
        System.out.println(findRotateSteps("abcde", "ade"));
        System.out.println(findRotateSteps("pqwcx", "cpqwx"));
        System.out.println(findRotateSteps("caotmcaataijjxi", "oatjiioicitatajtijciocjcaaxaaatmctxamacaamjjx"));
    }

    public static int findRotateSteps(String ring, String key) {
        int rLength = ring.length();
        int kLength = key.length();
        List<List<Integer>> indexs = new ArrayList<>(26);
        for(int i = 0;i < 26;i++){
            indexs.add(new ArrayList<>());
        }
        for(int i = 0;i < rLength;i++){
            indexs.get(ring.charAt(i) - 'a').add(i);
        }
        int[][] dp = new int[kLength][rLength];
        for(int i = 0;i < kLength;i++){
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        for (Integer integer : indexs.get(key.charAt(0) - 'a')) {
            dp[0][integer] = Math.min(integer, rLength - integer) + 1;
        }

        for(int i = 1;i < kLength;i++){
            for (Integer j : indexs.get(key.charAt(i) - 'a')) {
                for (Integer k : indexs.get(key.charAt(i - 1) - 'a')) {
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] +
                            Math.min(Math.abs(j - k), rLength - Math.abs(j - k)) + 1);
                }
            }
        }
        return Arrays.stream(dp[kLength - 1]).min().getAsInt();
    }
}
